package com.yq.leetcodeOld;

import com.yq.leetcodeOld.tree.ListNode;

/**
 * @ClassName ReverseList
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/4/8 11:25
 * @Version 1.0
 */
public class ReverseList {
    public static void main(String[] args) {
        //用迭代或递归方式完成反转

    }
    public ListNode reverseList(ListNode head){
        /**
         递归思路，一直递归到最后一个节点5， 它就是头，

        */

        if(head==null || head.next==null){ return head;}
        //假如12345，正向，会一直递归到4
        ListNode cur=reverseList(head.next);
        //将4的下一个5的下一个（本来为空）变成4 这样就形成了123454
        head.next.next=head;
        //这个位置将4的下一个指向5的这个关系断开， 形成了12354的链条
        head.next=null;
        //继续往回走，下一步去处理3，循环往复就得到了54321
        return cur;
    }
    public ListNode reverseList2(ListNode head){
        ListNode pre=null; ListNode cur =head;
        while (cur!=null){
            //迭代的思路，双指针，之前的pre和当前的cur，不断迭代，pre就是每次反转后的结果，cur=
            // 得到当前的就能把之前类似冒泡，对于当前节点，把当前的next存给temp， 把之前的pre给当然的next，pre被赋值为cur,cur继续把temp给到，向后移动
            //123456  比如当前是3 则temp就是4
            ListNode temp =cur.next; //把当前节点后面的给临时变量temp,后面再给cur,达到迭代的效果
            //这一步，就是把321456变成了432156
            cur.next=pre;
            // 这一步pre升华了从321变成了4321
            pre=cur;
            //这一步cur
            cur=temp;
        }
        return pre;
    }
}
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        ListNode pre=null;
//        ListNode cur=head;
//        while(cur!=null){
//            ListNode temp=cur.next;
//            cur.next=pre;
//            pre=cur;
//            cur=temp;
//        }
//        return pre;
//    }
//}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head==null || head.next==null){
//            return head;
//        };
//        ListNode cur=reverseList(head.next);
//        head.next.next=head;
//        head.next=null;
//        return cur;
//    }
//}